package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 1986. 完成任务的最少工作时间段
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/7 13:47
 */
public class MinSessions {

    public static void main(String[] args) {
        MinSessions test = new MinSessions();
        // 输入：tasks = [1,2,3], sessionTime = 3
        //输出：2

        // 2
//        int[] arr = {1,2,3};
//        int a = 3;

        // 2
//        int[] arr = {3, 1, 3, 1, 1};
//        int a = 8;

        // 1
//        int[] arr = {1,2,3,4,5};
//        int a = 15;

        //
        int[] arr = {2, 3, 6, 8, 9, 7, 6, 9, 8, 9, 8, 7, 9, 4};
        int a = 15;

        int i = test.minSessions(arr, a);
        System.out.println(i);
    }

    private int sessionTime;
    private int[] tasks;
    private int[] arr;
    private int length;
    private int[] flag;

    public int minSessions(int[] tasks, int sessionTime) {
        this.length = tasks.length;
        this.arr = new int[1 << length];
        this.flag = new int[length];
        this.tasks = tasks;
        this.sessionTime = sessionTime;
        for (int i = 0; i < length; i++) {
            flag[i] = 1 << i;
        }
        return find((1 << length) - 1) >> 16;
    }

    private int find(int index) {
        if (index == 0 || arr[index] != 0) {
            return arr[index];
        }
        int c = 16;
        int s = 0;
        for (int i = 0; i < length; i++) {
            if ((flag[i] & index) != 0) {
                int v = find(index - flag[i]);
                int t = tasks[i];
                int a = v >> 16;
                int b = v & 0XFFFF;
                if (t <= b) {
                    b -= t;
                } else {
                    a++;
                    b = sessionTime - t;
                }
                if (a <= c) {
                    c = a;
                    s = Math.max(s, b);
                }
            }
        }
        c = (c << 16) + s;
        arr[index] = c;
        return c;
    }

}
